1 Introduction

2 Preliminary Definitions

2.1 Notation and Conventions for Probabilistic Algorithms

notions

2.2 Game Networks and Distributed Algorithms

Probabilistic Distributed Alg.

2.3 Adversaries

Passive adversaries

• passive adversary
  • compute more than required don't want ro corrupt, but try to compute more than their due share of knowledge
  • msgs it sends and outputs are inaccordance to original program

Malicious Adv.

• malicious adversary
  • deviated from original progarm in any action
  • not only disrupte the privacy constraint
  • but also make the outcome different than in an ideal world

图灵游戏在any number of passive adv. or with n/2 malicious adv. 都是playable.

4 Hints on How to Play Hm-game With Passive Adversaries

4.1 A New and General OT Protocol

• A more general and useful notion of OT has been proposed by Even, Goldreich and Lempel: 1-out-of-2 OT

• proposed the first omplementation of a 1-out-of-2 OT using public key cryptosystems.

• requires a quite strong set of assumpeions even when the adversaries are only passive. 即使是在passive adv.面前也需要strong assumptions.

Our Protocol

为了简化处理，1-out-of-2 OT 中的msg只有1bit B不能预测另一个值，A不能预测B的选择。

• input:
  • A: a pair of bits (b0, b1) and their encryption.
  • B: private input bit $\alpha$

• desired properties:
  • B can read $b_\alpha$, but can't predict $b_{\overline{\alpha}}$
  • A cannot predict $\alpha$

1. (A) randomly select a trap-door function keep $f^{-1}$secret and sends f to B

2. (B) randomly selects $x_0, x_1$ sends A the pair (u, v)

3. (A)computes(c0, c1) use c to mask b and sends(d0, d1) to B

4. (B)computes $b_\alpha$

4.2 Strengthening Yao's Combined Oblivious Transfer

COT

• A, B: respectively owning private inputs a and b

• g: any chosen function g

• A computes g(a, b) while B don't know what A has computed

如果把a, b当作secrets，B obliviously transfer a prescribed combination of his and A's secret to A.

四行中只有一对的异或是密钥D5，其他都是密钥D6，解密0（AND gate) E1,E2,E5,E6和0，1的对应关系是public labelled E3,E4和0,1的关系是secretly labelled

1. (B)generates a COT AND-gate keep all decoding alg. and all strings in the rows

2. (B)gives A the second input-wire: b b可能是E3或E4，因为A不知道对应关系

3. (A)get either D1, D2 according to value a by 1-out-of-2 OT, B will not know which alg. A got

4. (A)easily compute the value of output-wire only A know AND(a,b)

4.3 The Tm-game Solver for passive adversaries

use CTO as a subrouting

• want to use COT as subrouting to construct a Tm-solver 想用COT作为Tm-solver的subrouting

• if two parties i and j use COT so that i will compute g(xi, yi) 通过COT,party i 可以计算g(xi, yi)，而party j 不知道。

[Ba]D. Barrington, Bounded-Width Branhing Program Recognize Exactly Those Languages in NC, Proc. 18th STOC, 1986 pp 1-5

用了一个symmetric group on 5 elements

in the program:

• 0和1都被分别编码为2个5-permutations

• 其中的变量都在S5中

• 程序中的每个操作都包含两个5-permutaions值都乘法，值可能是常量、变量或者变量的逆等。

each party:

• (input)takes private bits and encodes it by a 5-permutaion $\sigma$

• (divide $\sigma$)
  • selects n-1 random 5-permutaion and gives$(i,\sigma_i)$to party i i是index，最后结果计算时的乘积顺序
  • sets $\sigma_n$ and gives $(n,\sigma_n)$ to party n

each variable $\sigma$:

• each party x possesses an index permutation pair $(x, \sigma_x)$

• $\prod_{x=1}^n\sigma_x=\sigma$

通过以下指令，each party 可以计算最终结果的piece

Case 1: $\sigma\cdot c$

sigma is a variable and c is a constant

1. (each party) has a piece: $(x, \sigma_x)$

2. (party n) sets his new piece: $(n, \sigma_n\cdot c)$

3. (all each party) leaves his piece untouched

the ordered product of the new pieces is $\sigma\cdot c$ pieces按照顺序的乘积

Case 2: $\sigma^{-1}\cdot c$

求逆是逆序求，所以index需要改变 求出$\sigma^{-1}$，再按照case 1的情况处理

Case 3: $\sigma\cdot \tau$

• both $\sigma$ and $\tau$ are variables $\sigma\cdot \tau = \sigma_1\cdots\sigma_n\cdot \tau_1\cdots\tau_n$

• each party poseesses piece $\sigma_i$ and $\tau_i$

• S5 is not commutative party i在计算最终结果piece时，不能直接将两个piece相乘，因为S5是不满足交换律的。

giving new pieces

move party 1's pieces closer by swaping 通过交换，让party 1的两个pieces靠近

• $\sigma_1\sigma_2\tau_1\tau_2$: swap $\sigma_2$ and $\tau_1$
  • $\sigma_1\tau_1'\sigma_2'\tau_2$ : satisfy $\sigma_2\tau_1=\tau_1'\sigma_2'$ 交换后，each party就可以将his pieces 相乘，得到最终结果的piece。计算结果时，按序相乘即可。

• $\sigma_1\cdots\sigma_n\cdot \tau_1\cdots\tau_n$: swap $\sigma_n$ and $\tau_1$
  • move party 1's pieces closer
    1. swap $\sigma_{n}$ and $\tau_1$: $\sigma_1\cdots\sigma_{n-1}\tau_1'\cdot \sigma_n'\cdots\tau_n$ satisfy $\sigma_n\tau_1=\tau_1'\sigma_n'$
    2. swap $\sigma_{n-1}$ and $\tau_1'$ swap party n-1's piece and party 1's piece
    3. ...go on swapping
    4. (party 1 final)$\sigma_1\cdot \tau_1'\cdots\sigma_{n-1}'\cdot \sigma_n'\tau_2\cdots\tau_n$
  • move party 2's pieces closer
  • final: $\sigma_1\cdot \tau_1'\cdots\cdots\sigma_n'\tau_n$

$\sigma_n\tau_1=\tau_1'\sigma_n'$

• violate the privacy constraint: party 1 and party n tell each other $\sigma_n$and $\tau_1$ 其中一种实现new pieces的方法是party n和party 1互相告知对应的pieces，但这会破坏隐私性

respect the privacy constraint use COT to achieve $\sigma_n\tau_1=\tau_1'\sigma_n'$

1. (party n)randomly selects a 5-permutation $\rho$
   1. party 1 posesses: $\sigma_1,\tau_1$
   2. party n posesses: $\sigma_n, \tau_n, \rho$

2. function g: for 5-permutations x, y and z $g(x,(y,z))=w \quad\text{where }wz=yx$

3. COT
   1. A(party 1): input $a=\tau_1$
   2. B(party n): input $b=(\sigma_n,\rho)$
   3. A(party 1)'s output: $g(a,b)$
   4. B(party n)'s output: none

4. set new pieces:
   1. party 1 : $\sigma_1, \tau_1'=g(a,b)$
   2. party n: $\sigma_n'=\rho,\tau_n$
   3. $\tau_1'\sigma_n'=g(a,b)\cdot\rho=\sigma_n\tau_1$

Analyze security informally

• party n has no info about party 1's old piece nor the now one
  • party n's new piece is a random $\rho$
  • transfer g(a, b) is oblivious

• party 1 has no info about party n'
  • $g(\tau_1,(\sigma_n,\rho))$ : party 1 only knows $\tau_1$
  • $g(x,(y,\cdot)$ is injective on S5 and $\rho$ is randomly selected by party n

Complexity

• after n 'swaps': party 1 can get the pieces for the variable $\sigma\cdot \tau$

• $\mathcal{O}(n^2)$

End